package a_doubleWrite;

import util.ListNode;

/**
 * 143. 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 *  L0 → L1 → … → Ln-1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * @author luolidong
 * @version 1.0
 * @create 2021-07-28 09:16
 */
public class L143 {
     public void reorderList(ListNode head) {
         //获取中点
         ListNode left=head,right=head;
         while (right!=null&&right.next!=null){
             left=left.next;
             right=right.next.next;
         }
         //断开
         ListNode newHead=left.next;
         left.next=null;

         //反转单链表
         ListNode newHead1=reverse(newHead);
         //重新构造
         ListNode cur=head;
         while (cur!=null&&newHead1!=null){
             ListNode secondCur=newHead1;
             newHead1=secondCur.next;

             ListNode curNode=cur;
             cur=curNode.next;

             curNode.next=secondCur;
             secondCur.next=cur;
         }

     }
     public ListNode reverse(ListNode root){
         if(root.next==null) return root;
         ListNode cur=root,pre=null;
         while (cur!=null){
             ListNode next=cur.next;
             cur.next=pre;
             pre=cur;
             cur=next;
         }
         return pre;
     }
}
